//  All code copyright (c) 2003 Barry Lapthorn
//  Website:  http://www.lapthorn.net
//
//  Disclaimer:  
//  All code is provided on an "AS IS" basis, without warranty. The author 
//  makes no representation, or warranty, either express or implied, with 
//  respect to the code, its quality, accuracy, or fitness for a specific 
//  purpose. Therefore, the author shall not have any liability to you or any 
//  other person or entity with respect to any liability, loss, or damage 
//  caused or alleged to have been caused directly or indirectly by the code
//  provided.  This includes, but is not limited to, interruption of service, 
//  loss of data, loss of profits, or consequential damages from the use of 
//  this code.
//
//
//  $Author: barry $
//  $Revision: 1.1 $
//
//  $Id: GA.cs,v 1.1 2003/08/19 20:59:05 barry Exp $
//
//  Modified by Lionel Monnier 30th aug 2004

#region Using directives

using System;
using System.Collections.Generic;

#endregion

namespace Salesman.Genetic
{
    /// <summary>
    /// Genetic Algorithm abstract class. Inherit to create an implementation. Default constructor sets mutation rate to 5%, crossover to 80%, population to 100,
    /// genome size to 64 and generations to 2000.
    /// </summary>
    public abstract class GA
    {
        public const int DefaultGenomeSize = 64;

        //private static FittnessFunction getFitness;
        private readonly Random random = new Random();
        private double crossoverRate = 0.80;
        private bool elitism = false;
        private List<double> fitnessTable;
        private int generationSize = 2000;
        //private int m_genomeMax;
        private List<Genome> nextGeneration;
        private int populationSize = 100;

        private List<Genome> thisGeneration;
        private double totalFitness;
        private double mutationRate = 0.05;

        #region Properties

        //  Properties
        protected int PopulationSize
        {
            get { return populationSize; }
            set { populationSize = value; }
        }

        protected int Generations
        {
            get { return generationSize; }
            set { generationSize = value; }
        }

        protected double CrossoverRate
        {
            get { return crossoverRate; }
            set { crossoverRate = value; }
        }

        /// <summary>
        /// Keep previous generation's fittest individual in place of worst in current
        /// </summary>
        protected bool Elitism
        {
            get { return elitism; }
            set { elitism = value; }
        }

        protected Random Randomizer
        {
            get { return random; }
        }

        public double MutationRate
        {
            get { return mutationRate; }
            set { mutationRate = value; }
        }
        /// <summary>
        /// Maximum value which can be genome
        /// </summary>
        //public int GenomeMax
        //{
        //    get { return m_genomeMax; }
        //    set { m_genomeMax = value; }
        //}

        #endregion

        protected abstract double Fitness(Genome genome);
        protected virtual void OnNextGeneration()
        {
        }
        protected virtual void OnGo()
        {
        }

    
        /// <summary>
        /// Method which starts the GA executing.
        /// </summary>
        public void Go()
        {
            //  Create the fitness table.
            fitnessTable = new List<double>();
            thisGeneration = new List<Genome>(generationSize);
            nextGeneration = new List<Genome>(generationSize);


            CreateGenomes();
            RankPopulation();

            OnGo();
            for (int i = 0; i < generationSize; i++) {
                CreateNextGeneration();
                RankPopulation();
                OnNextGeneration(); // fire event
            }
        }

        /// <summary>
        /// After ranking all the genomes by fitness, use a 'roulette wheel' selection
        /// method.  This allocates a large probability of selection to those with the 
        /// highest fitness.
        /// </summary>
        /// <returns>Random individual biased towards highest fitness</returns>
        private int RouletteSelection()
        {
            double randomFitness = Randomizer.NextDouble() * totalFitness;
            int idx = -1;
            int mid;
            int first = 0;
            int last = populationSize - 1;
            mid = (last - first) / 2;

            //  ArrayList's BinarySearch is for exact values only
            //  so do this by hand.
            while (idx == -1 && first <= last) {
                if (randomFitness < fitnessTable[mid]) {
                    last = mid;
                }
                else if (randomFitness > fitnessTable[mid]) {
                    first = mid;
                }
                mid = (first + last) / 2;
                //  lies between i and i+1
                if ((last - first) == 1)
                    idx = last;
            }
            return idx;
        }

        /// <summary>
        /// Rank population and sort in order of fitness.
        /// </summary>
        private void RankPopulation()
        {
            totalFitness = 0.0;
            foreach (Genome g in thisGeneration) {
                g.Fitness = Fitness(g);
                totalFitness += g.Fitness;
            }
            thisGeneration.Sort((x, y) => x.Fitness.CompareTo(y.Fitness));

            //  now sorted in order of fitness.
            //double fitness = 0.0;
            fitnessTable.Clear();
            foreach (Genome t in thisGeneration) {
                //fitness += t.Fitness;
                fitnessTable.Add(t.Fitness);
            }
        }

        /// <summary>
        /// Create the *initial* genomes by repeated calling the supplied fitness function
        /// </summary>
        private void CreateGenomes()
        {
            for (int i = 0; i < populationSize; i++) {
                Genome g = CreateGenome();
                thisGeneration.Add(g);
            }
        }

        protected abstract Genome CreateGenome();

        private void CreateNextGeneration()
        {
            nextGeneration.Clear();
            Genome g = null;
            if (elitism)
                g = thisGeneration[populationSize - 1].Clone();

            for (int i = 0; i < populationSize; i += 2) {
                int pidx1 = RouletteSelection();
                int pidx2 = RouletteSelection();
                Genome parent1, parent2, child1, child2;
                parent1 = thisGeneration[pidx1];
                parent2 = thisGeneration[pidx2];

                if (Randomizer.NextDouble() < crossoverRate) {
                    parent1.CrossOverWith(parent2, out child1, out child2);
                }
                else {
                    child1 = parent1;
                    child2 = parent2;
                }
                child1.Mutate(mutationRate);
                child2.Mutate(mutationRate);

                nextGeneration.Add(child1);
                nextGeneration.Add(child2);
            }
            if (elitism && g != null)
                nextGeneration[0] = g;

            thisGeneration.Clear();
            foreach (Genome ge in nextGeneration)
                thisGeneration.Add(ge);
        }

        public void GetBest(out Genome genome, out double fitness)
        {
            Genome g = thisGeneration[populationSize - 1];
            fitness = g.Fitness;
            genome = g.Clone();
        }

        public void GetWorst(out Genome genome, out double fitness)
        {
            GetNthGenome(0, out genome, out fitness);
        }

        public void GetNthGenome(int n, out Genome genome, out double fitness)
        {
            /// Preconditions
            /// -------------
            if (n < 0 || n > populationSize - 1)
                throw new ArgumentOutOfRangeException("n");
            /// -------------
            Genome g = thisGeneration[n];
            genome = g.Clone();
            fitness = g.Fitness;
        }
    }
}